home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / TARFILE.GZ / tarfile / ch_4.3 / xcc / cc.c next >
C/C++ Source or Header  |  1999-09-11  |  28KB  |  1,008 lines
  1. /* 
  2.  * cc.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * C(enter)C(ircular disks)
  11.  *
  12.  * functions required in determination of center positions of circular disks
  13.  */
  14.  
  15. #include "xcc.h"
  16.  
  17. #define    OFF        0
  18. #define    ON        1
  19.  
  20. #define    NEW        1                  /* flag to indicate init of new dsk */
  21. #define    CUR        0
  22.  
  23. #define    LEFT        -1
  24. #define    RIGHT        1
  25.  
  26. #define    R_COMP        1               /* methods to estimate ctr r-coord */
  27. #define    INTERS        2
  28. #define    METHOD        INTERS
  29.  
  30. #define    MAX_INDEX    255
  31.  
  32. #define    ID_OVLP_LM    0.1          /* cut-off for ``ideal'' circles */
  33. #define    AP_OVLP_LM    3.0
  34. #define    OVLP_LM        AP_OVLP_LM
  35. #define    SHIFT_LM    OVLP_LM        /* cut-off for rel segm pos (``shift'') */
  36.  
  37.  
  38. #undef DPRINT
  39. #undef    DBG
  40. #undef SHOW_NEW_ADISK
  41. #undef    DBG_ENC_ROW
  42. #undef    DBG_OVLP
  43. #undef    DBG_SYMM_OVLP
  44. #undef    DBG_INSP
  45. #undef    DBG_EVAL_CTR
  46.  
  47. /* globals */
  48. extern int del_ir;
  49. extern float ddia;
  50.  
  51.  
  52.  
  53. /*
  54.  * initialize new disk structure (the structure itself already exists)
  55.  */
  56. int
  57. init_disk (struct disk *ndsk, int nch)
  58. {
  59.   int ich;
  60.  
  61.  
  62.   if ((ndsk->chords = (struct triple *) calloc (nch + 1, sizeof (struct triple))) == NULL) {
  63.     printf ("\n...mem alloc for *ndsk->chords failed!!\n");
  64.     return (0);
  65.   }
  66.  
  67. /* initialize structure */
  68.   ndsk->nch = 0;
  69.   ndsk->ctr.y = ndsk->ctr.x = -1;
  70.   ndsk->rad = -1;
  71.   ndsk->Status = Active;
  72.   ndsk->Type = Accept;
  73.  
  74.   for (ich = 0; ich < nch; ich++) {
  75.     ndsk->chords[ich].r = -1;
  76.     ndsk->chords[ich].cl = ndsk->chords[ich].cr = -1;
  77.   }
  78.   return (1);
  79. }
  80.  
  81. /*
  82.  * set current disk to InActive status
  83.  */
  84. int
  85. close_disk (struct disk *cdsk)
  86. {
  87.  
  88.   if ((cdsk->Status == Active)) {
  89.     cdsk->Status = InActive;
  90.     return (1);
  91.   }
  92.   else {
  93.     printf ("\nCLOSE_DISK: cur disk not Active\n");
  94.     return (0);
  95.   }
  96. }
  97.  
  98.  
  99.  
  100. /*
  101.  * set current disk to Reject type
  102.  */
  103. int
  104. flag_disk (struct disk *cdsk)
  105. {
  106.  
  107.   if ((cdsk->Type == Accept)) {
  108.     cdsk->Type = Reject;
  109.     return (1);
  110.   }
  111.   else {
  112.     printf ("\nFLAG_DISK: cur disk type not Accept\n");
  113.     return (0);
  114.   }
  115. }
  116.  
  117.  
  118. /*
  119.  * fetch set of coefficients for 1d edge detector
  120.  */
  121. void
  122. fetch_edge_det (float *ef, int nf)
  123. {
  124. }
  125.  
  126.  
  127.  
  128. /*
  129.  * apply edge detection filter to input array, y, via cyclic (1d)
  130.  * convolution; return result in input array;
  131.  */
  132. void
  133. edge_det (unsigned char *y, int n, float *f, int nf)
  134. {
  135.   double *yy;
  136.  
  137.   /*
  138.    * to be implemented
  139.    */
  140.   if ((yy = (double *) calloc (n, sizeof (double))) == NULL) {
  141.     printf ("\n...mem alloc for array yy of type double failed");
  142.     exit (1);
  143.   }
  144.  
  145.   free (yy);
  146. }
  147.  
  148.  
  149. /*
  150.  * given symmetric overlap between the current edge tuple and the last
  151.  * chord in the array of chords associated with the Active disk currently
  152.  * under inspection, determine whether to add cetpl to cdsk:
  153.  * given cetpl and disk_dia, compute center positions for the two circles
  154.  * of which cetpl may form a chord (one center position lying above, the
  155.  * other below the current row); compare the estimate(s) so derived with
  156.  * those computed in the same way for cdsk_ldchrd (in the case that
  157.  * cdsk only contains that one chord) or with the center coordinates
  158.  * currently stored in cdsk; test the separation between row-coordinates
  159.  * (the column coordinate passes trivially, given the condition of symmetric 
  160.  * overlap !!), to make a decision about acceptance of cetpl into cdsk;
  161.  *
  162.  * in comparing row coordinates of potential center positions, take
  163.  * advantage of simple geometrical facts, given that cetpl follows 
  164.  * cdsk_lchrd in the raster scan; thus if (cre-cle) >= (crc-clc), cetpl and 
  165.  * cdsk_lchrd can only be part of the same circle if that circle's center 
  166.  * r-coordinate exceeds rc; hence, only ruc need be inspected; the analogous 
  167.  * conclusion holds if (cre-cle) <= (crc-clc): cetpl and cdsk_lchrd can
  168.  * only be part of the same circle if the center r-coordinate is smaller
  169.  * than re; hence, only rle need be inspected;
  170.  */
  171. Boolean
  172. insp_Adsk (int ir, struct edge_tuple *cetpl, struct disk *cdsk)
  173. {
  174.   struct triple *cdsk_lchrd;
  175.  
  176.   double rue, rle;
  177.   double rc, ruc, rlc;
  178.   double del_ce, del_cc;
  179.   double dcr, ec_r;
  180.   double min_r_dist;
  181.  
  182.   Boolean AccRejStat;
  183.  
  184.  
  185. /* initialize variables */
  186.  
  187.   cdsk_lchrd = &cdsk->chords[(cdsk->nch) - 1];
  188.  
  189.   del_ce = (double) (cetpl->cr - cetpl->cl);
  190.   del_cc = (double) (cdsk_lchrd->cr - cdsk_lchrd->cl);
  191.  
  192.  
  193. #ifdef DBG_INSP
  194.   printf ("INSP_ADSK -- estimate ctr r-coord: METHOD %d\n", METHOD);
  195. #endif
  196.  
  197. /* 
  198.  * estimate coordinates of circle center, based on those already stored in 
  199.  * cdsk and the vertex coords of cetpl; the column coord is trivially found 
  200.  * based on symmetry, the r-coord requires more effort;
  201.  *
  202.  * two methods are employed, depending on whether cdsk contains
  203.  * only a single chord or several (more than one) chord
  204.  * 
  205.  * Method 1:
  206.  * ---------
  207.  * compare the four possible center r-coords, a pair each derived from
  208.  * the disk chord and from cetpl, relying on the initial estimate, disk_dia
  209.  * of the disk size; this is robust only in the absence of contour noise
  210.  * Method 2:
  211.  * ---------
  212.  * construct the normal to each of the line segments {(re, cle), (rc, clc)}
  213.  * and {(re, cre), (rc, crc)} and find the r-coords of their intersection
  214.  * point(s) with the line d(isk)c(center)c == 0.5(clc+crc)=const (which 
  215.  * contains the disk center); given dcc, the desired r-coords are readily 
  216.  * found by evaluating pertinent slopes;
  217.  */
  218.  
  219.   switch (METHOD) {
  220.   case 1:
  221.     rue = (double) ir + 0.5 * sqrt (SQR (ddia) - SQR (del_ce));
  222.     rle = (double) ir - 0.5 * sqrt (SQR (ddia) - SQR (del_ce));
  223.  
  224.     if (cdsk->nch == 1) {
  225.       rc = (double) cdsk->chords[(cdsk->nch) - 1].r;
  226.       ruc = rc + 0.5 * sqrt (SQR (ddia) - SQR (del_cc));
  227.       rlc = rc - 0.5 * sqrt (SQR (ddia) - SQR (del_cc));
  228.  
  229.       if ((del_ce - del_cc) >= SHIFT_LM) {  /* etpl > chord */
  230.         if (MIN (fabs (rue - ruc), fabs (rle - ruc)) < del_ir)
  231.           AccRejStat = Pass;
  232.         else
  233.           AccRejStat = Fail;
  234.       }
  235.       if ((del_cc - del_ce) >= SHIFT_LM) {  /* chord > etpl */
  236.         if ((min_r_dist = MIN (fabs (ruc - rle), fabs (rlc - rle))) < del_ir)
  237.           AccRejStat = Pass;
  238.         else
  239.           AccRejStat = Fail;
  240.       }
  241.     }
  242.     else {
  243.       dcr = (double) cdsk->ctr.y;
  244.  
  245.       if ((min_r_dist = MIN (fabs (rue - dcr), fabs (rle - dcr))) < del_ir)
  246.         AccRejStat = Pass;
  247.       else
  248.         AccRejStat = Fail;
  249.     }
  250.  
  251. #ifdef DBG_INSP
  252.     if (cdsk->nch == 1) {
  253.       printf ("   ctr r-coord derived from chrd, ddia:\n");
  254.       printf ("     ruc=%lf, rlc=%lf\n", ruc, rlc);
  255.     }
  256.     else {
  257.       printf ("   ctr r-coord derived from etpl, ddia:\n");
  258.       printf ("     rue=%lf, rle=%lf\n", rue, rle);
  259.     }
  260.     printf ("-->min r-dist to estim center: %lf\n", min_r_dist);
  261. #endif
  262.     break;
  263.  
  264.   case 2:
  265.  
  266.     ec_r = pbi_ctr (ir, cetpl, cdsk_lchrd);  /* est ctr r-coord */
  267.  
  268.     if (cdsk->nch == 1) {
  269.       rc = (double) cdsk->chords[(cdsk->nch) - 1].r;
  270.       ruc = rc + 0.5 * sqrt (SQR (ddia) - SQR (del_cc));
  271.       rlc = rc - 0.5 * sqrt (SQR (ddia) - SQR (del_cc));
  272.  
  273.       if ((min_r_dist = MIN (fabs (ruc - ec_r), fabs (rlc - ec_r))) < del_ir)
  274.         AccRejStat = Pass;
  275.       else
  276.         AccRejStat = Fail;
  277.     }
  278.     else {
  279.       dcr = (double) cdsk->ctr.y;
  280.  
  281.       if ((min_r_dist = fabs (dcr - ec_r)) < del_ir)
  282.         AccRejStat = Pass;
  283.       else
  284.         AccRejStat = Fail;
  285.     }
  286.  
  287. #ifdef DBG_INSP
  288.     if (cdsk->nch == 1) {
  289.       printf ("   ctr r-coord derived from chrd, ddia:\n");
  290.       printf ("     ruc=%lf, rlc=%lf\n", ruc, rlc);
  291.     }
  292.     else {
  293.       printf ("   cdsk cur ctr r-coord: dcr=%lf,\n", dcr);
  294.     }
  295.     printf ("   ctr r-coord from inters of perp bis: ");
  296.     printf (" ec_r=%lf\n", ec_r);
  297.     printf ("-->min r-dist to estim center: %lf\n", min_r_dist);
  298. #endif
  299.     break;
  300.   }
  301.   return (AccRejStat);
  302. }
  303.  
  304.  
  305. /*
  306.  * find latest entry in chord array of current disk
  307.  */
  308. int
  309. find_cdsk_lchrd (int ir, struct disk *cdsk)
  310. {
  311.   int chrd_row;
  312.  
  313.  
  314.   if (cdsk->nch == 0) {
  315.     printf ("   current disk structure empty\n");
  316.     return (-1);
  317.   }
  318.   else if (((chrd_row = cdsk->chords[cdsk->nch - 1].r) != ir - del_ir) &&
  319.            (chrd_row != ir)) {
  320. #ifdef DPRINT
  321.     printf ("FIND_CDSK_LCHRD -- WARNING: ");
  322.     printf ("--> row %3d out of order -- disk chord index: %3d\n",
  323.             chrd_row, cdsk->nch - 1);
  324. #endif
  325.     return (-1);
  326.   }
  327.   else {
  328.     return (cdsk->nch - 1);     /* return index of last filled chrd */
  329.   }
  330. }
  331.  
  332.  
  333. /*
  334.  * find all Active disks currently listed in dll:
  335.  *
  336.  * proceeding from list tail, reset dll list pointer to the position of
  337.  * the ``oldest'' remaining Active disk which, by construction, is the
  338.  * disk most distant from the tail of the list; an efficient way to
  339.  * find the desired position entails ''rewinding'' the current list pointer
  340.  * until either
  341.  * -->the first InActive disk is encountered: 
  342.  *   set AdskStatus to Fail, advance list pointer to point to Active disk
  343.  *           
  344.  * or
  345.  * -->the head of dll is reached (without encountering any InActive disk):
  346.  *           AdskStatus remains True, list pointer points to Active disk
  347.  */
  348. struct linktype *
  349. find_all_Adsks (struct linklist *dll)
  350. {
  351.   struct disk *cdsk;
  352.   int nad, ndll;
  353.   Boolean DllStatus;
  354.   Boolean AdskStatus;
  355.  
  356.   lltail (dll);
  357.   if ((ndll = ll_length (dll)) == 0)
  358.     return (dll->clp);
  359.  
  360. #ifdef DPRINT
  361.   printf ("\nFIND_ALL_ADSKS -- rewind dll\n");
  362. #endif
  363.   nad = 0;
  364.   DllStatus = AdskStatus = True;
  365.   do {
  366.     if ((cdsk = (struct disk *) dll->clp->item)->Status == Active) {
  367. #ifdef DPRINT
  368.       printf (" %d ", ++nad);
  369. #endif
  370.       DllStatus = llprevious (dll);
  371.     }
  372.     else
  373.       AdskStatus = False;
  374.  
  375.   } while ((DllStatus == True) && (AdskStatus == True));
  376.   if (AdskStatus == False)
  377.     llnext (dll);
  378.  
  379. #ifdef DPRINT
  380.   printf ("\n...rewinding dll (AdskStatus: %d)", AdskStatus);
  381.   printf (" -->identified %d Active disks\n", nad);
  382. #endif
  383.  
  384.   return (dll->clp);
  385. }
  386.  
  387.  
  388. /*
  389.  * find next disk in dll with Active status
  390.  */
  391. struct linktype *
  392. find_next_Adsk (struct linklist *dll)
  393. {
  394.   struct disk *cdsk;
  395.  
  396.   while (llnext (dll) == True) {
  397.     if ((cdsk = (struct disk *) dll->clp->item)->Status == Active)
  398.       return (dll->clp);
  399.  
  400.   }
  401.  
  402.   return ((struct linktype *) NULL);
  403. }
  404.  
  405.  
  406. /*
  407.  * add new disk structure to tail of dll, reset list pointer to original pos
  408.  */
  409. void
  410. app_ndsk_to_dll (char *ndsk, struct linklist *dll)
  411. {
  412.   struct linktype *adlp;
  413.  
  414.   adlp = dll->clp;
  415.   lltail (dll);
  416.   lladd ((char *) ndsk, dll);
  417.   dll->clp = adlp;
  418. }
  419.  
  420.  
  421. /*
  422.  * insert new disk structure into dll so as to retain the list of Active
  423.  * disks in the order of increasing etpl column coordinates; reset list 
  424.  * pointer to original pos
  425.  */
  426. void
  427. ins_ndsk_to_dll (char *ndsk, struct linklist *dll, int shift)
  428. {
  429.   struct linktype *adlp;
  430.  
  431.   adlp = dll->clp;
  432.   if (shift == LEFT)
  433.     lladdprev ((char *) ndsk, dll);
  434.   if (shift == RIGHT)
  435.     lladd ((char *) ndsk, dll);
  436.   dll->clp = adlp;
  437. }
  438.  
  439.  
  440.  
  441.  
  442. /*
  443.  * add new chord, converted from edge tuple, to disks's array of chords;
  444.  * the disk may be a currently Active disk already containing chords or 
  445.  * a newly initialized disk 
  446.  */
  447. Boolean
  448. chord_to_Adsk (int ir, int nch, struct edge_tuple *cetpl, struct disk *cdsk, int disk_type, int ncch)
  449. {
  450.   struct triple *cdsk_lchrd;
  451.  
  452.   int memalloc;
  453.   int cl, cr;
  454.   int cctr_r, nctr_r;
  455.  
  456.   if (disk_type == NEW) {       /* init new disk */
  457.     if ((memalloc = init_disk (cdsk, nch)) == 0) {
  458. #ifdef DPRINT
  459.       printf ("\nCHORD_TO_DISK -- disk init failed\n");
  460. #endif
  461.       return (Fail);
  462.     }
  463.   }
  464.   else {                        /* posit chord array ptr of cur dsk */
  465.     if (cdsk->Status != Active) {
  466.       printf ("\nCHORD_TO_ADISK -- cur disk must be Active\n");
  467.       return (Fail);
  468.     }
  469.   }
  470.  
  471. /* store etpl in cdsk */
  472.  
  473.   cdsk->chords[ncch].r = ir;
  474.   cdsk->chords[ncch].cl = cetpl->cl;
  475.   cdsk->chords[ncch].cr = cetpl->cr;
  476.   cdsk->nch++;
  477.  
  478.  
  479. /* 
  480.  * update circle center pos and radius
  481.  */
  482.   if (cdsk->nch == 1) {         /* first estim of cntr pos and rad */
  483.     cl = cdsk->chords[cdsk->nch - 1].cl;
  484.     cr = cdsk->chords[cdsk->nch - 1].cr;
  485.  
  486.     cdsk->ctr.y = (short) (ir + 0.5 * sqrt (SQR (ddia) - SQR (cr - cl)));
  487.     cdsk->ctr.x = (cetpl->cl + cetpl->cr) / 2;
  488.     cdsk->rad = F_TO_INT (0.5 * ddia);
  489.   }
  490.   else {
  491.     cdsk_lchrd = &cdsk->chords[(cdsk->nch) - 2];
  492.     nctr_r = F_TO_INT (pbi_ctr (ir, cetpl, cdsk_lchrd));
  493.     if (cdsk->nch == 2)
  494.       cdsk->ctr.y = nctr_r;
  495.     else {
  496.       cctr_r = cdsk->ctr.y;
  497. #ifdef DPRINT
  498.       printf ("\n...cctr_r: %d, nctr_r: %d\n", cctr_r, nctr_r);
  499. #endif
  500.       cdsk->ctr.y = ((cdsk->nch - 1) * cctr_r + nctr_r) / cdsk->nch;
  501.     }
  502.     cdsk->rad = eval_rad (cdsk);
  503. #ifdef DPRINT
  504.     printf ("\n...ctr y_coord just stored in cdsk: %3d\n", cdsk->ctr.y);
  505.     printf ("...estimated radius: %d\n", cdsk->rad);
  506. #endif
  507.   }
  508.  
  509.  
  510. #ifdef SHOW_NEW_ADISK
  511.   printf ("\nCHORD_TO_ADISK: ");
  512.   if (disk_type == NEW)
  513.     printf ("initialize new Active disk\n");
  514.   else
  515.     printf ("update existing Active disk\n");
  516.   printf ("   nof chords in curr Active disk: %d\n", cdsk->nch);
  517.   printf ("   last (%d-th) chord: [%3d; %3d %3d]\n", ncch,
  518.           cdsk->chords[cdsk->nch - 1].r,
  519.           cdsk->chords[cdsk->nch - 1].cl,
  520.           cdsk->chords[cdsk->nch - 1].cr);
  521. #endif
  522.  
  523.   return (Pass);
  524. }
  525.  
  526.  
  527.  
  528. /*
  529.  * determine relative displacement (along rows) of segments with partial 
  530.  * or vanishing overlap (see find_segm_ovlp())
  531.  *
  532.  * LEFT/RIGHT: etpl left/right-shifted w/r chord
  533.  */
  534. int
  535. find_segm_shift (struct triple *chrd, struct edge_tuple *cetpl)
  536. {
  537.  
  538.   if (chrd->cl >= cetpl->cr)
  539.     return (LEFT);
  540.   if (cetpl->cl >= chrd->cr)
  541.     return (RIGHT);
  542.  
  543. }
  544.  
  545.  
  546. /*
  547.  * given two segments, one disk chord, one edge tuple on successive
  548.  * scan lines, establish their mode of overlap: the ovlp flag serves
  549.  * to distinguish three cases: 
  550.  *
  551.  * -- ovlp = 0: if no overlap exists, the disk containing the current chord
  552.  *           is set Inactive; however, a new disk to hold the current edge 
  553.  *           tuple is not yet called for: the edge tuple may still belong 
  554.  *           to another Active disk which would, however, have to lie 
  555.  *           between the current chord and the edge tuple;
  556.  *
  557.  * -- ovlp =-1: finite partial overlap obtains, so that
  558.  *
  559.  *                   yO_et < yO_dc < yF_et < yF_dc,
  560.  *           or
  561.  *                   yO_dc < yO_et < yF_dc < yF_et;
  562.  *
  563.  *           in either case, a new disk must be inserted into dll to 
  564.  *           hold the current edge tuple as a chord; the disk containing 
  565.  *           the current disk chord is closed (given Inactive status);
  566.  *           finite overlap obtains if the following two inequalities hold:
  567.  *
  568.  *                   yO_et < yF_dc and yO_dc < yF_et,
  569.  *
  570.  *           or vice versa; otherwise, there is no overlap: -->case 0;
  571.  *           complete overlap is ensured if, in addition to the previous 
  572.  *           inequality, yF_dc < yF_et, or vice versa
  573.  *
  574.  * -- ovlp = 1: only if one segment symmetrically encloses the other, that is,
  575.  *           if, given complete overlap, one has in addition,
  576.  *
  577.  *                   abs( yO_dc - yO_et ) = abs( yF_et - yF_dc )
  578.  *
  579.  *           or, alternatively,
  580.  *
  581.  *                   (yO_dc + yF_dc)/2 = (yO_et + yF_et)/2
  582.  *
  583.  *           does the edge_tuple qualify for further consideration as an 
  584.  *           additional disk chord; 
  585.  */
  586. int
  587. find_segm_ovlp (struct triple *chrd, struct edge_tuple *cetpl)
  588. {
  589.   int ovlp = 77;
  590.   int yOe, yFe, yOc, yFc;
  591.  
  592.   yOc = (int) chrd->cl;
  593.   yFc = (int) chrd->cr;
  594.   yOe = (int) cetpl->cl;
  595.   yFe = (int) cetpl->cr;
  596.  
  597. #ifdef DBG_OVLP
  598.   printf ("FIND_SEGM_OVLP: ");
  599. #endif
  600.   if ((yOe < yFc) && (yOc < yFe)) {  /* partial ovlp */
  601.     if ((yOe <= yOc) && (yFc <= yFe)) {  /* etpl encl chrd */
  602.       if (fabs ((yOc + yFc) - (yOe + yFe)) < OVLP_LM)
  603.         ovlp = 1;
  604.     }
  605.     else if ((yOc <= yOe) && (yFe <= yFc)) {  /* chrd encl etpl */
  606.       if (fabs ((yOc + yFc) - (yOe + yFe)) < OVLP_LM)
  607.         ovlp = 1;
  608.     }
  609.     else
  610.       ovlp = -1;                /* finite partial ovlp */
  611.  
  612.   }
  613.   else                          /* no ovlp */
  614.     ovlp = 0;
  615.  
  616. #ifdef DBG_OVLP
  617.   printf (" %d\n", ovlp);
  618. #endif
  619.  
  620.   return (ovlp);
  621. }
  622.  
  623.  
  624.  
  625. /*
  626.  * process current edge tuple list, generated in last row scan,
  627.  * by assigning edge tuples to disk structures, either to currently
  628.  * Active (Incomplete) or to new disks, to be added to disk list;
  629.  * Active disks to which no new edge tuple is assigned are given 
  630.  * Inactive (Complete) status
  631.  */
  632. int
  633. update_disk_list (int ir, int nch, struct linklist *dll, struct linklist *etll)
  634. {
  635.   struct linktype *adlp;        /* ptr to first Act disk in dll */
  636.   struct linktype *sadlp;       /* ptr to save init val of adlp */
  637.   struct linktype *stdlp;       /* ptr to save init val of dll->tail */
  638.   struct disk *cdsk;            /* pointer to disk at cur dll posit */
  639.   struct disk new_disk, *ndsk = &new_disk;
  640.  
  641.   struct edge_tuple *cetpl;
  642.  
  643.  
  644.   int nnad;                     /* nof Act disks added to dll */
  645.   int ncd;                      /* nof Act disks closed in cur pass */
  646.   int nfd;                      /* nof Act disks set to type Reject */
  647.   int etll_to_dll = OFF;
  648.  
  649.   int ovlp;
  650.   //int shift;        /* used with ins_ndsk_to_dll() */
  651.   int ncch;                     /* ind of last filled chrd in cdsk */
  652.   Boolean AccRejStat;           /* test status (Pass/Fail) of etpl */
  653.  
  654. /* 
  655.  * scan (col-ordered) edge_tuple list, etll, and update the array of chords 
  656.  * associated with each disk: this may require inserting new disk structures
  657.  * into dll, as well as updating disk structures already present in the list 
  658.  *
  659.  * the emerging list contains disk structures in the order of their
  660.  * acquiring Active (Open) status: a new disk, with Active status, is 
  661.  * added to dll, whenever an edge tuple on the current scan line does not
  662.  * satisfy the overlap conditions which would identify it as a chord of one
  663.  * of the already Active disks; the edge tuple under consideration is entered
  664.  * as a chord of a new disk structure which is in turn inserted into dll;
  665.  * any disk which is not intersected by the current scan line (and thus 
  666.  * acquires no new chord) is given InActive status;
  667.  *
  668.  * two modes of insertion with different advantages may be considered:
  669.  * -- insert new disk at at the end (tail) of dll --> app_ndsk_to_dll();
  670.  *    dll is doubly sorted: primary key is the row-coord of its first chord,
  671.  *    secondary key is the col-coord of chords on the same row; this has the
  672.  *    advantage of maintaining Active disks in a contiguous sequence at the
  673.  *    end of dll and thus makes it easy to locate all Active disks
  674.  * -- insert new disk in according to results of comparing ovlp and shift 
  675.  *    (--> find_segm_shift()) of cdsk_lchrd and etpl --> ins_ndsk_to_dll();
  676.  *    dll is sorted according to the col-coord of its first chord; this has
  677.  *    the advantage of requiring only local operations of ovlp and segm
  678.  *    evaluations when examining a new etpl: only the c-adjacent disks need
  679.  *    be inspected; however, it has the disadvantage of fragmenting the 
  680.  *    Active portion of dll
  681.  * -->possible room for speed-ups at a later stage of development
  682.  */
  683. #ifdef DPRINT
  684.   printf ("\n\nUPDATE_DISKLIST -- process new etll\n");
  685. #endif
  686.   if (ll_length (etll) == 0) {
  687. #ifdef DPRINT
  688.     printf ("\nUPDATE_DISK_LIST -- edge_tuple list empty\n");
  689.     printf (" -->no update of disk list required\n");
  690. #endif
  691.  
  692.     return (0);
  693.   }
  694.  
  695. /* 
  696.  * etll not empty: update disk list; find all Incomplete (Active) disks
  697.  * by resetting dll to last Active disk, i.e. the Active disk farthest 
  698.  * from the tail of dll
  699.  */
  700.   sadlp = dll->head;
  701.   stdlp = dll->tail;
  702.   if ((adlp = find_all_Adsks (dll)) == stdlp) {
  703.     if (ll_length (dll) == 0) {
  704. #ifdef DPRINT
  705.       printf ("\n...currently no Active disks in dll\n");
  706.       printf (" -->cp all chords in etll into Act disk in dll\n");
  707.  
  708. #endif
  709.       etll_to_dll = ON;         /* copy etll to dll */
  710.     }
  711.   }
  712.  
  713.  
  714.   llhead (etll);
  715.   cetpl = (struct edge_tuple *) etll->clp->item;
  716.   sadlp = adlp;
  717.   nnad = 0;
  718.   do {                          /* scan etll */
  719.     /* process segm with matched status */
  720. #ifdef DPRINT
  721.     printf ("\nUPDATE_DISK_LIST -- process new etpl\n");
  722. #endif
  723.     cetpl = (struct edge_tuple *) etll->clp->item;
  724.     if (cetpl->status != Matched)
  725.       return (0);
  726.  
  727.     if (etll_to_dll == ON) {    /* enter cur etpl into dll */
  728.       AccRejStat = chord_to_Adsk (ir, nch, cetpl, ndsk, NEW, 0);
  729.  
  730.       app_ndsk_to_dll ((char *) ndsk, dll);
  731.       nnad++;
  732.     }
  733.  
  734. /*
  735.  * advance dll->clp by one to point to first Active disk in dll
  736.  * (note: mem alloc for an Active disk has already been performed, see above!)
  737.  *
  738.  * determine ovlp between etpl and disk chord (see function find_segm_ovlp());
  739.  * also examine the relative positioning of etpl and chrd: this serves to
  740.  * insert new disks into dll in increasing order of segment column coords
  741.  *
  742.  * etpl l-shifted w/r chrd, i.e. etpl precedes chrd:
  743.  *   open new disk struct preceding cdsk to hold current tuple
  744.  *   maintain cdsk Active
  745.  * etpl r-shifted w/r chrd, i.e., chrd precedes etpl:
  746.  *   set cdsk InActive
  747.  *   retain current etpl and check ovlp with next Adsk in dll 
  748.  */
  749.     else {                      /* check overlap betw cur etpl, dsk chords */
  750.       dll->clp = sadlp;
  751.       AccRejStat = Fail;
  752.       do {                      /* scan Adsks in dll */
  753.         adlp = dll->clp;
  754.         cdsk = (struct disk *) adlp->item;
  755.         if ((ncch = find_cdsk_lchrd (ir, cdsk)) == -1) {
  756. #ifdef DPRINT
  757.           printf ("\nUPDATE_DISK_LIST -- ");
  758.           printf (" WARNING: row coords of last disk chord incorrect\n");
  759.           printf ("    ir: %3d, del_ir: %3d\n", ir, del_ir);
  760.           /* PROC ERR: halt execution!! */
  761. #endif
  762.         }
  763.  
  764.         ovlp = find_segm_ovlp (&(cdsk->chords[cdsk->nch - 1]), cetpl);
  765.         if (ovlp == 1) {        /* symmetric */
  766.           if ((AccRejStat = insp_Adsk (ir, cetpl, cdsk)) == Pass) {
  767.             chord_to_Adsk (ir, nch, cetpl, cdsk, CUR, ncch + 1);
  768.           }
  769.           else {
  770.             /* PROC ERR */
  771.             AccRejStat = chord_to_Adsk (ir, nch, cetpl, ndsk, NEW, 0);
  772.             app_ndsk_to_dll ((char *) ndsk, dll);
  773.             nnad++;
  774.  
  775.           }
  776.         }
  777.  
  778.       } while ((AccRejStat == Fail) && (llnext (dll) == True));
  779.  
  780.       /* reached tail of dll without inserting etpl */
  781.       if (AccRejStat == Fail) {
  782. #ifdef DPRINT
  783.         printf ("\nUPDATE_DISK_LIST -- ");
  784.         printf (" append new disk to dll\n");
  785. #endif
  786.         AccRejStat = chord_to_Adsk (ir, nch, cetpl, ndsk, NEW, 0);
  787.         app_ndsk_to_dll ((char *) ndsk, dll);
  788.         nnad++;
  789.       }
  790.     }
  791.   } while (llnext (etll) == True);
  792.  
  793.  
  794. /* 
  795.  * etll exhausted: inspect all Active disks which were present in dll prior 
  796.  * to processing the current etll, that is those between positions pointed
  797.  * to by sadlp and stdlp; disks which were not updated in the current pass
  798.  * (by receiving an etll segment as a new chord) must be closed
  799.  */
  800. #ifdef DPRINT
  801.   printf ("\nUPDATE_DISK_LIST -- etll (row %3d) exhausted\n", ir);
  802. #endif
  803.   dll->clp = sadlp;
  804.   ncd = nfd = 0;
  805.   if (etll_to_dll == ON)
  806.     return (nnad);
  807.  
  808.   do {
  809.     if ((cdsk = (struct disk *) dll->clp->item)->Status == Active) {
  810.       if (cdsk->nch == nch) {   /* max nof chords attained */
  811.         ncd += close_disk (cdsk);
  812.       }
  813.       else {
  814.         if ((ncch = find_cdsk_lchrd (ir + del_ir, cdsk)) == -1) {
  815.           ncd += close_disk (cdsk);
  816.  
  817. /* 
  818.  * additional Type-checking may be performed here to Reject disks
  819.  * 
  820.  * example: 
  821.  *  -- segments of disks clipped by left or right edges all have identical
  822.  *     cl or cr coordinates which may be used to discriminate 
  823.  */
  824.  
  825. /*
  826.  * note: counting segments is not a robust criterion to identify clipped
  827.  *    disks in the presence of size variations
  828.  *
  829.  * if( cdsk->nch < nch-1 )      
  830.  * nfd += flag_disk(cdsk);
  831.  */
  832.  
  833.         }
  834.       }
  835.     }
  836.   } while (llnext (dll) == True);
  837. #ifdef DPRINT
  838.   printf ("...closed %d disk(s), flagged %d disks\n", ncd, nfd);
  839. #endif
  840.  
  841.   return (nnad);
  842. }
  843.  
  844. /*
  845.  * determine and set status (Matched/UnMatched) currently last entry 
  846.  * in edge tuple list
  847.  */
  848. Boolean
  849. ReptSegmStatus (struct edge_tuple * letpl, int pix)
  850. {
  851.   Boolean Segm_Status;
  852.  
  853.  
  854.   Segm_Status = letpl->status;
  855.   switch (pix) {
  856.   case OFF:                    /* OFF->ON: last tuple Matched? */
  857.  
  858.     if (Segm_Status == UnMatched) {
  859. #ifdef DPRINT
  860.       printf ("\n...OFF->ON: last entry in etll UnMatched:");
  861.  
  862.       if (letpl->cr == -1)
  863.         printf ("...cr invalid\n");
  864.       else
  865.         printf ("...unknown origin\n");
  866. #endif
  867.     }
  868.     else if (Segm_Status == Matched) {  /* OK */
  869.     }
  870.     else {
  871.       Segm_Status = UnKnown;
  872. #ifdef DPRINT
  873.       printf ("\n...OFF->ON: segm status UnKnown\n");
  874. #endif
  875.     }
  876.     break;
  877.  
  878.   case ON:                     /* ON->OFF: last tuple UnMatched */
  879.  
  880.     if (Segm_Status == Matched) {
  881. #ifdef DPRINT
  882.       printf ("\n...ON->OFF: last entry in etll already Matched: cr = %3d\n",
  883.               (int) letpl->cr);
  884. #endif
  885.     }
  886.     else if (Segm_Status == UnMatched) {  /* OK */
  887.     }
  888.     else {
  889.       Segm_Status = UnKnown;
  890. #ifdef DPRINT
  891.       printf ("\n...ON->OFF: segm status UnKnown\n");
  892. #endif
  893.     }
  894.     break;
  895.   }
  896.   return (Segm_Status);
  897. }
  898.  
  899.  
  900. /*
  901.  * given a row extracted from the original image (GRAY_LEV = BNRY), or
  902.  * an extracted row which has been subjected to 1d edge detection,
  903.  * locate edge points and place successive edge points into tuples 
  904.  * (cl: OFF->ON transition, cr: ON->OFF transition); each such edge tuple 
  905.  * gives the y-coordinates delimiting ON-segments (``runs''); the status 
  906.  * of a segment is Matched if the pair {cl, cr} marks successive OFF->ON, 
  907.  * ON->OFF transitions in image intensity; otherwise, the segment status is 
  908.  * UnMatched; edge tuples are entered into a y-ordered edge tuple list;
  909.  */
  910. int
  911. encode_row (unsigned char *row, int nc, struct linklist *etll, int gray_lev)
  912. {
  913.   int jc;
  914.   int pix;
  915.   struct edge_tuple cur_etpl, *cetpl = &cur_etpl;
  916.   Boolean Etpl_Status;
  917.  
  918.  
  919.   if (gray_lev == 0) {          /* binary input row */
  920.  
  921.     lltail (etll);
  922.     Etpl_Status = Matched;
  923.     cetpl->cl = cetpl->cr = -1;
  924.     cetpl->status = UnMatched;
  925.     pix = OFF;
  926.  
  927.     jc = 0;
  928.     while (jc < nc) {
  929.       if (*(row + jc) / MAX_INDEX == pix)
  930.         jc++;
  931.  
  932.       else {
  933.  
  934.         switch (pix) {
  935.  
  936.         case OFF:              /* handle OFF->ON transition */
  937.  
  938.           /* initialize new ON-segm */
  939.           cetpl->cl = jc + 1;
  940.           cetpl->cr = -1;
  941.           cetpl->status = UnMatched;
  942.  
  943. #ifdef DPRINT
  944.           printf ("...jc=%3d: edge tup [%3d %3d] init",
  945.                   jc, cetpl->cl, cetpl->cr);
  946. #endif
  947.  
  948.           /* enter new tuple into edge_tuple_list */
  949.           lltail (etll);
  950.  
  951.           /* status of last ON-segm Matched? */
  952.           if (ll_length (etll) > 0) {
  953.             Etpl_Status = ReptSegmStatus ((struct edge_tuple *) etll->clp->item, pix);
  954. #ifdef DPRINT
  955.             if (Etpl_Status != Matched)
  956.               printf ("\nWARNING: prev ON-segm not Matched\n");
  957. #endif
  958.           }
  959.           lladd ((char *) cetpl, etll);
  960. #ifdef DPRINT
  961.           printf ("...entered into etll");
  962.           printf (" -->cur list len: %d\n", ll_length (etll));
  963. #endif
  964.  
  965.           pix = ON;
  966.           break;
  967.  
  968.         case ON:               /* handle ON->OFF transition */
  969.  
  970.           /* complete current ON-segm */
  971.           lltail (etll);
  972.  
  973.           /* status of last ON-segm UnMatched? */
  974.           if (ll_length (etll) > 0) {
  975.             Etpl_Status = ReptSegmStatus ((struct edge_tuple *) etll->clp->item, pix);
  976.             if (Etpl_Status != UnMatched)
  977.               printf ("\nWARNING: prev ON-segm not UnMatched\n");
  978.           }
  979.           ((struct edge_tuple *) etll->clp->item)->cr = jc;
  980.           ((struct edge_tuple *) etll->clp->item)->status = Matched;
  981.  
  982. #ifdef DPRINT
  983.           printf ("...jc=%3d: edge tup [%3d %3d] compl", jc, ((struct edge_tuple *) etll->clp->item)->cl,
  984.                   ((struct edge_tuple *) etll->clp->item)->cr);
  985.  
  986.           printf (" -->cur list len: %d\n", ll_length (etll));
  987. #endif
  988.  
  989.           pix = OFF;
  990.           break;
  991.         }
  992.       }
  993.     }
  994.   }
  995.   else if (gray_lev == 1) {
  996.     printf ("\n...1d edge detection: to be implemented\n");
  997.   }
  998.  
  999.  
  1000. #ifdef DBG_ENC_ROW
  1001.   printf ("\nCC.C: display current edge tuple list\n");
  1002.   show_etpl_list (etll);
  1003. #endif
  1004.  
  1005.  
  1006.   return (etll->listlength);
  1007. }
  1008.